#pragma once
#include<iostream>
using namespace std;

namespace key{
	template<class T>
	struct TreeNode {
		T val;
		TreeNode* left;
		TreeNode* right;

		TreeNode(const T& x)
			:val(x)
			, left(nullptr)
			, right(nullptr)
		{}
	};

	template<class T>
	class BSTree {
		typedef TreeNode<T> Node;
	public:
		Node* Find(const T& x)
		{
			Node* cur = _root;
			while (cur)
			{
				if (x < cur->val)
					cur = cur->left;
				else if (x > cur->val)
					cur = cur->right;
				else
					return cur;
			}
			return nullptr;
		}

		bool insert(const T& x)
		{
			if (_root == nullptr)
			{
				_root = new Node(x);
				return true;
			}
			Node* cur = _root, * fa = nullptr;
			while (cur)
			{
				fa = cur;
				if (x < cur->val)
					cur = cur->left;
				else if (x > cur->val)
					cur = cur->right;
				else
					return false;
			}
			if (x < fa->val)
				fa->left = new Node(x);
			else
				fa->right = new Node(x);
			return true;
		}

		bool erase(const T& x)
		{
			Node* cur = _root, * fa = nullptr;
			while (cur)
			{

				if (x < cur->val)
				{
					cur = cur->left;
					fa = cur;
				}
				else if (x > cur->val)
				{
					cur = cur->right;
					fa = cur;
				}
				else
				{
					if (cur->left == nullptr)
					{
						if (x < fa->val)
							fa->left = cur->right;
						else
							fa->right = cur->right;
					}
					else if (cur->right == nullptr)
					{
						if (x < fa->val)
							fa->left = cur->left;
						else
							fa->right = cur->left;
					}
					else
					{
						Node* suf = cur->right;
						Node* suf_fa = cur;
						while (suf->left)
						{
							suf_fa = suf;
							suf = suf->left;
						}
						swap(cur->val, suf->val);
						if (suf_fa == cur)
						{
							cur->right = suf->right;
						}
						else
						{
							suf_fa->left = nullptr;
						}
						cur = suf;
					}
					delete cur;
					return true;
				}
			}
			return true;
		}

		void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}

		BSTree() = default;
		BSTree(const BSTree& t)
		{
			_root = Copy(t._root);
		}

		BSTree& operator=(const BSTree t)
		{
			swap(_root, t._root);
			return *this;
		}

		~BSTree()
		{
			Destroy(_root);
		}
	private:
		void Destroy(Node*& root)
		{
			if (root == nullptr)
				return;
			Destroy(root->left);
			Destroy(root->right);
			delete root;
			root = nullptr;
		}

		Node* Copy(Node* root)
		{
			if (root == nullptr)
				return nullptr;
			Node* newnode = new Node(root->val);
			newnode->left = Copy(root->left);
			newnode->right = Copy(root->right);
			return newnode;
		}

		void _InOrder(Node* root)
		{
			if (root == nullptr)
				return;
			_InOrder(root->left);
			cout << root->val << " ";
			_InOrder(root->right);
		}

	private:
		Node* _root;
	};
}


namespace kv {
	template<class T,class V>
	struct TreeNode {
		T key;
		V val;
		TreeNode* left;
		TreeNode* right;

		TreeNode(const T& k,const V& v)
			:key(k)
			,val(v)
			, left(nullptr)
			, right(nullptr)
		{}
	};

	template<class T,class V>
	class BSTree {
		typedef TreeNode<T,V> Node;
	public:
		Node* Find(const T& x)
		{
			Node* cur = _root;
			while (cur)
			{
				if (x < cur->key)
					cur = cur->left;
				else if (x > cur->key)
					cur = cur->right;
				else
					return cur;
			}
			return nullptr;
		}

		bool insert(const T& x,const V& y)
		{
			if (_root == nullptr)
			{
				_root = new Node(x,y);
				return true;
			}
			Node* cur = _root, * fa = nullptr;
			while (cur)
			{
				fa = cur;
				if (x < cur->key)
					cur = cur->left;
				else if (x > cur->key)
					cur = cur->right;
				else
					return false;
			}
			if (x < fa->key)
				fa->left = new Node(x,y);
			else
				fa->right = new Node(x,y);
			return true;
		}

		bool erase(const T& x)
		{
			Node* cur = _root, * fa = nullptr;
			while (cur)
			{

				if (x < cur->key)
				{
					cur = cur->left;
					fa = cur;
				}
				else if (x > cur->key)
				{
					cur = cur->right;
					fa = cur;
				}
				else
				{
					if (cur->left == nullptr)
					{
						if (x < fa->key)
							fa->left = cur->right;
						else
							fa->right = cur->right;
					}
					else if (cur->right == nullptr)
					{
						if (x < fa->key)
							fa->left = cur->left;
						else
							fa->right = cur->left;
					}
					else
					{
						Node* suf = cur->right;
						Node* suf_fa = cur;
						while (suf->left)
						{
							suf_fa = suf;
							suf = suf->left;
						}
						swap(cur->key, suf->key);
						swap(cur->val, suf->val);
						if (suf_fa == cur)
						{
							cur->right = suf->right;
						}
						else
						{
							suf_fa->left = nullptr;
						}
						cur = suf;
					}
					delete cur;
					return true;
				}
			}
			return true;
		}

		void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}

		BSTree() = default;
		BSTree(const BSTree& t)
		{
			_root = Copy(t._root);
		}

		BSTree& operator=(const BSTree t)
		{
			swap(_root, t._root);
			return *this;
		}

		~BSTree()
		{
			Destroy(_root);
		}


		Node* find_r(const T& x)
		{
			return _find_r(_root, x);
		}

		bool insert_r(const T& x,const V& y)
		{
			return _insert_r(_root, x, y);
		}

		bool erase_r(const T& x)
		{
			return _erase_r(_root, x);
		}
	private:
		bool _erase_r(Node*&root,const T& x)
		{
			if (root == nullptr)
				return false;
			if (x < root->key)
				return _erase_r(root->left, x);
			else if (x > root->key)
				return _erase_r(root->right, x);
			else
			{
				if (root->left == nullptr)
				{
					Node* del = root;
					root = root->right;
					delete del;
					return true;
				}
				else if (root->right == nullptr)
				{
					Node* del = root;
					root = root->left;
					delete del;
					return true;
				}
				else
				{
					Node* suf = root->right;
					while (suf->left)
						suf = suf->left;
					swap(suf->key, root->key);
					swap(suf->val, root->val);
					return _erase_r(root->right, x);
				}
			}
		}
		bool _insert_r(Node*& root, const T& x, const V& y)
		{
			if (root == nullptr)
			{
				root = new Node(x, y);
				return true;
			}
			if (x < root->key)
				return _insert_r(root->left, x, y);
			else if (x > root->key)
				return _insert_r(root->right, x, y);
			else
				return false;
		}

		Node* _find_r(Node* root, const T& x)
		{
			if (root == nullptr)
				return nullptr;
			if (x < root->key)
				return _find_r(root->left, x);
			else if (x > root->key)
				return _find_r(root->right, x);
			else
				return root;
		}
		void Destroy(Node*& root)
		{
			if (root == nullptr)
				return;
			Destroy(root->left);
			Destroy(root->right);
			delete root;
			root = nullptr;
		}

		Node* Copy(Node* root)
		{
			if (root == nullptr)
				return nullptr;
			Node* newnode = new Node(root->key,root->val);
			newnode->left = Copy(root->left);
			newnode->right = Copy(root->right);
			return newnode;
		}

		void _InOrder(Node* root)
		{
			if (root == nullptr)
				return;
			_InOrder(root->left);
			cout << root->key << ":" << root->val << endl;
			_InOrder(root->right);
		}

	private:
		Node* _root;
	};
}